#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    bool ans1(vector<int>& nums, int k){
        unordered_map<int, vector<int>> map;
        for(int i = 0; i != nums.size(); i++){
            map[nums[i]].push_back(i);
        }
        for(auto it = map.begin(); it != map.end(); it++){
            if(it->second.size() > 1){
                for(int i = 0; i != it->second.size()-1; i++){
                    int m = INT16_MAX;
                    m = min(it->second[i+1]-it->second[i], m);
                    if(m <= k){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    //更简单的方式
    bool ans2(vector<int>& nums, int k){
        unordered_map<int, int> map;
        for(int i = 0; i != nums.size(); i++){
            int num = nums[i];
            if(map.count(num) && i - map[num] <= k){
                return true;
            }
            map[num] = i;
        }
        return false;
    }

};

void test1(){
    Solution s;
    vector<int> nums = {1,2,3,1};
    int target = 3;
    // bool ret = s.ans1(nums, target);
    bool ret = s.ans2(nums, target);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {1,0,1,1};
    int target = 1;
    // bool ret = s.ans1(nums, target);
    bool ret = s.ans2(nums, target);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<int> nums = {1,2,3,1,2,3};
    int target = 2;
    // bool ret = s.ans1(nums, target);
    bool ret = s.ans2(nums, target);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}